package com.zklh.leetcode.dfs;

import com.zklh.leetcode.tree.model.TreeNode;

import java.util.*;

/**
 * 路径总和2
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2022/5/26 16:19
 */
public class Solution113 {
    private List<List<Integer>> paths = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        LinkedList<Integer> path = new LinkedList<>();
        dfs(path, root, 0, targetSum);
        return paths;
    }

    public void dfs(LinkedList<Integer> path, TreeNode root, int sum, int targetSum) {
        if (root == null) {
           return;
        }
        path.addLast(root.val);
        sum += root.val;
        if (root.left == null && root.right == null && sum == targetSum) {
            addPath(path);
        }

        dfs(path, root.left, sum, targetSum);
        dfs(path, root.right, sum, targetSum);
        path.removeLast();
    }

    public void addPath(LinkedList<Integer> path) {
        paths.add(new ArrayList<>(path));
    }

    public static void main(String[] args) {

    }
}
